class Node(object):
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []


class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        if not node:
            return []
        head = Node(node.val)
        search_node = {head.val: head}
        head_neighbors = []
        search_list = node.neighbors
        for item in search_list:
            node = Node(item.val)
            head_neighbors.append(node)
            search_node[item.val] = node
        head.neighbors = head_neighbors
        create_list = head_neighbors
        while search_list:
            new_search_list = []
            new_create_list = []
            for i in range(len(search_list)):
                new_node_list = []
                for j in range(len(search_list[i].neighbors)):
                    if search_list[i].neighbors[j].val in search_node:
                        new_node_list.append(search_node[search_list[i].neighbors[j].val])
                    else:
                        node = Node(search_list[i].neighbors[j].val)
                        new_node_list.append(node)
                        new_create_list.append(node)
                        new_search_list.append(search_list[i].neighbors[j])
                        search_node[node.val] = node
                create_list[i].neighbors = new_node_list
            search_list = new_search_list
            create_list = new_create_list
        return head






